package org.ymx.myHeap;

public class MyHeapCSDN {

}

class Node {
    private int e;

    public Node(int e) {
        this.e = e;
    }

    public int getE() {
        return this.e;
    }

    public void setE(int e) {
        this.e = e;
    }
}

class Heap<AnyType> {
    private Node[] heapArray;
    private int maxSize;//容量
    private int size;//当前大小

    public Heap(int maxSize) {
        this.maxSize = maxSize;
        size = 0;
        heapArray = new Node[maxSize];
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public boolean insert(int e) {
        if (size >= maxSize) {
            return false;
        }
        Node newNode = new Node(e);
        heapArray[size] = newNode;
        trickleUp(size);
        size++;
        return true;
    }

    //插入新节点的时，先把新节点插入最后，再向上调整，下面是向上调整的函数
    public void trickleUp(int index) {
        int parent = (index - 1) / 2;
        Node bottom = heapArray[index];//保存一份新插入的节点
        while (index > 0 && bottom.getE() > heapArray[parent].getE()) {
            heapArray[index] = heapArray[parent];//孩子比父亲大，把父亲给孩子，往下面拉，腾出位置
            index = parent;//继续往上找
            parent = (parent - 1) / 2;
        }
        heapArray[index] = bottom;
    }

    public Node remove() {
        if (0 == size) {
            return null;
        }
        Node root = heapArray[0];
        heapArray[0] = heapArray[--size];
        trickleDown(0);//下移
        return root;
    }

    public void trickleDown(int index) {
        int largerChild;
        Node top = heapArray[index];
        while (index < size / 2) {//仍存在非叶子节点的时候，一个有n个节点的完全二叉树的非叶子节点树是size/2(商)
            int leftChild = 2 * index + 1;
            int rightChild = leftChild + 1;
            //从左右两个孩子中找一个较大的孩子，注意有孩子未必存在，需要判定
            if (rightChild < size && heapArray[leftChild].getE() < heapArray[rightChild].getE()) {
                largerChild = rightChild;
            } else {
                largerChild = leftChild;
            }

            if (top.getE() >= heapArray[largerChild].getE()) {
                break;
            }

            heapArray[index] = heapArray[largerChild];//把比父母大的孩子上移到父母处
            index = largerChild;
        }
        heapArray[index] = top;
    }

    public boolean change(int index, int newE) {
        if (index < 0 || index >= size) {
            return false;
        }
        int oldE = heapArray[index].getE();
        heapArray[index].setE(newE);
        if (newE > oldE) {
            trickleUp(index);
        } else {
            trickleDown(index);
        }
        return true;
    }

    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.print(heapArray[i].getE() + " ");
        }
        System.out.println();
    }
}

class Main {

    public static void main(String[] args) {
        Heap heap = new Heap(10);
        int[] a = {4, 1, 3, 6, 9, 7};
        for (int i = 0; i < a.length; i++) {
            heap.insert(a[i]);
        }
        heap.print();
        System.out.println(heap.remove().getE() + " removed.");
        heap.print();
        heap.change(2, 66);
        heap.print();
    }

}
